;; Non-robust Jarvis march algorithm for computing the convex hull of a set of 2D points.
;; Copyright (C) 2021  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.compgeom.convex-hull.jarvis-march
  (:require [mazama.compgeom.core :refer [distance-squared point-orient2d]]))

;;;; NOTE
;;;;
;;;; 1. This software may fail if floating point values are used.
;;;;
;;;; 2. This software assumes that:
;;;;    the x-axis increases to the right;
;;;;    the y-axis increases DOWNWARD.

(defn- left-most-point-fn [[x1 y1 :as p1] [x2 y2 :as p2]]
  (cond
    (< x1 x2) p1
    (< x2 x1) p2
    (< y1 y2) p1
    :else p2))

(defn- left-most-point [S]
  (reduce left-most-point-fn S))

(defn- march-fn
  "Consider the directed line from point `a` through point `b`:
  if `c` is to the right of the line then return `c`;
  else if `c` is to the left of the line then return `b`;
  otherwise return `b` or `c`, whichever is furthest from `a`."
  [a b c]
  (case (point-orient2d a b c)
    -1 c
    0 (let [dist-b (distance-squared a b)
            dist-c (distance-squared a c)]
        (if (> dist-c dist-b)
          c
          b))
    1 b))

(defn- march
  "Return the next point on the hull of `S` given the `most-recent-point-on-hull`."
  [S most-recent-point-on-hull]
  (reduce (partial march-fn most-recent-point-on-hull) (first S) (rest S)))

(defn convex-hull
  "Compute the convex hull of the 2D points in `S`.
  https://en.wikipedia.org/wiki/Gift_wrapping_algorithm"
  [S]
  (if (< (count S) 3)
    S
    (let [initial-point-on-hull (left-most-point S)]
      (loop [hull (vector initial-point-on-hull)
             most-recent-point-on-hull (peek hull)]
        (let [next-point-on-hull (march S most-recent-point-on-hull)]
          (if (= next-point-on-hull initial-point-on-hull)
            hull
            (recur (conj hull next-point-on-hull) next-point-on-hull)))))))
